// AntiClockwise.java

/*
 * 本类实现逆时针的方阵遍历：
 */
public class AntiClockwise extends SquareTraversal{
    public AntiClockwise(int size) {
        initiate(size);
    }

    @Override public SquarePoint getInitPoint() {
        return new SquarePoint(0, 0);
    }

    @Override
    public SquarePoint getNext() {
    // 在这里添加代码
        // 在这里添加代码

        SquarePoint currentPoint = currentPath.get(currentPath.size() - 1);

        int currRow = currentPoint.getRow();
        int currCol = currentPoint.getCol();
        int nextRow = 0;
        int nextCol = 0;

        // 如果已经遍历完所有元素
        if (currentPath.size() == size * size) {
            return null;
        }

        // 定义四个方向：下、右、上、左
        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int directionIndex = 0;

        // 比较前一个点的坐标确定当前方向
        if (currentPath.size() > 1) {
            SquarePoint prev = currentPath.get(currentPath.size() - 2);
            int dRow = currRow - prev.getRow();
            int dCol = currCol - prev.getCol();

            for (int i = 0; i < directions.length; i++) {
                if (directions[i][0] == dRow && directions[i][1] == dCol) {
                    directionIndex = i;
                    break;
                }
            }
        }

        // 尝试沿当前方向移动
        nextRow = currRow + directions[directionIndex][0];
        nextCol = currCol + directions[directionIndex][1];

        // 检查是否需要转向
        if (nextRow < 0 || nextRow >= size || nextCol < 0 || nextCol >= size ||
                isVisited(nextRow, nextCol)) {
            // 顺时针转向
            directionIndex = (directionIndex + 1) % 4;
            nextRow = currRow + directions[directionIndex][0];
            nextCol = currCol + directions[directionIndex][1];
        }

        return new SquarePoint(nextRow, nextCol);
    }

    private boolean isVisited(int row, int col) {
        for (SquarePoint point : currentPath) {
            if (point.getRow() == row && point.getCol() == col) {
                return true;
            }
        }
        return false;
    }
}